#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System.Collections.Generic;
using AbstractClass.Collections.Generic;

namespace AbstractClass.Collections.Graph
{
    /// <summary>
    /// Represents a minimal spanning tree algorithm applicable on a <see cref="Graph&lt;T&gt;"/>.
    /// </summary>
    /// <typeparam name="T">The type of the data in the <see cref="Graph&lt;T&gt;"/>.</typeparam>
    public class MinimalSpanningTree<T> : IAlgorithm<Graph<T>, Graph<T>>
    {
        #region Implementation of IAlgorithm<in Graph<T>,out Graph<T>>

        /// <summary>
        /// Gets a minimal spanning tree of a <see cref="Graph&lt;T&gt;"/> specified by <paramref name="substrate"/>.
        /// </summary>
        /// <param name="substrate">A <see cref="Graph&lt;T&gt;"/> object whose minimal spanning tree needs to be calculated.</param>
        /// <returns>
        /// A <see cref="Graph&lt;T&gt;"/> which represents the minimal spanning tree of the <paramref name="substrate"/>.
        /// </returns>
        public Graph<T> Run(Graph<T> substrate)
        {
            int edgeCount = substrate.NodeList.Count - 1;
            var vertexToParent = new Dictionary<GraphNode<T>, GraphNode<T>>();
            var oldToNew = new Dictionary<GraphNode<T>, GraphNode<T>>();

            var edgeQueue = new Heap<KeyValuePair<double, GraphEdge<T>>>(HeapType.Minimum,
                                                                         new KeyValueComparer<double, GraphEdge<T>>());
            var returnGraph = new Graph<T>();

            foreach (var vertex in substrate.NodeList)
            {
                var vertex2 = vertex.Clone() as GraphNode<T>;
                oldToNew.Add(vertex, vertex2);
                returnGraph.Add(vertex2);

                vertexToParent.Add(vertex, null);
            }

            foreach (var graphEdge in substrate.Edges)
            {
                edgeQueue.Add(new KeyValuePair<double, GraphEdge<T>>(graphEdge.Cost, graphEdge));
            }

            while ((edgeQueue.Count > 0) && (edgeCount > 0))
            {
                KeyValuePair<double, GraphEdge<T>> association = edgeQueue.RemoveItem();
                GraphEdge<T> edge = association.Value;

                GraphNode<T> fromVertexHead = edge.Source;
                GraphNode<T> toVertexHead = edge.Destination;

                while (vertexToParent[fromVertexHead] != null)
                {
                    fromVertexHead = vertexToParent[fromVertexHead];
                }

                while (vertexToParent[toVertexHead] != null)
                {
                    toVertexHead = vertexToParent[toVertexHead];
                }

                if (fromVertexHead == toVertexHead) continue;
                vertexToParent[fromVertexHead] = edge.Destination;
                edgeCount--;
                returnGraph.AddUndirectedEdge(oldToNew[edge.Source], oldToNew[edge.Destination], edge.Cost);
            }

            return returnGraph;
        }

        #endregion
    }
}